/*
 * Jiri Cigler
 * ciglej1@fel.cvut.cz 
 *
 * Copyright (C) 2007 Jirka Cigler <ciglej1@fel.cvut.cz>
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
 * USA
 */ 

#include "scheduler.hh"
#include <algorithm>
#include <vector>
using namespace std;

vector<Activity> listOfActivities;
vector<SortTableElement> sortTable;

void reindex(){
	int i=0;
	for(std::vector<Activity>::iterator it = listOfActivities.begin(); it!= listOfActivities.end(); it++){
		sortTable.push_back(SortTableElement(it->id,i));
		it->id = i;
		i++;
	};
	std::sort(sortTable.begin(), sortTable.end());
	for(std::vector<Activity>::iterator it = listOfActivities.begin(); it!= listOfActivities.end(); it++){
		for(std::vector<unsigned int>::iterator it1 = it->prerequirements.begin(); it1!=it->prerequirements.end(); it1++){
			*it1 = sortTable.at(*it1).actual;
		}
	};	
};


void init(int **& resource, unsigned int **& duration, int iJobs, int iTasksInJob){
	//listOfActivities.clear();
//	sortTable.clear();
	int res, processingTime,i,j, id;
	id =0;
	//fill list of activities
	for( i=0; i < iJobs; i++ ){
		for(j = 0; j < iTasksInJob; j++){
			res = resource[i][j];
			processingTime = duration[i][j];
			listOfActivities.push_back(Activity(processingTime,res,id++));
			if(j!=0)
				(listOfActivities.end()-1)->prerequirements.push_back((listOfActivities.begin()+(i*iTasksInJob+j-1))->id);
		};
	};

	//Setting up last task	
	listOfActivities.push_back(Activity(0,0,listOfActivities.size()));
	for(int i = 1 ; i <= iJobs; i++)
		listOfActivities.at(listOfActivities.size()-1).prerequirements.push_back(listOfActivities.at(i*iTasksInJob -1).id);

	//sort by resource
	std::sort(listOfActivities.begin(), listOfActivities.end());

	reindex();
};

void run(int **& resource, unsigned int **& duration, const
		 int jobs, int tasksInJob, int machines
		, unsigned int **& result,double * runtime) {
	
	init(resource,duration,jobs, tasksInJob);

	unsigned int minTime = 0;
	unsigned int t = 0;
	
	for(int i=0; i < jobs ; ++i){
		t = 0;
		for(int j = 0; j <tasksInJob;++j){
			t+=duration[i][j];	
		};
		if(t > minTime)
			minTime = t;		
	};
	unsigned int maxTime = 0;
	for(int i=0; i < jobs ; ++i){
		for(int j = 0; j <tasksInJob;++j){
			maxTime+=duration[i][j];	
		}
	};
	unsigned int c_d = Search::Config::c_d;
	unsigned int a_d = Search::Config::a_d;
	unsigned int solutions = 0;
	int fails= 10000000;
	int time = -1;
	bool solution = false;
	try {

		Timer t;
		t.start();
		
		while(!solution){
			int i = solutions;
			cout << "\n minTime = " << minTime << "\n"<< endl;
			//Scheduler* s = new Scheduler(resource, duration, jobs, tasksInJob, machines,	maxTime);
			Scheduler* s = new Scheduler(resource, duration, jobs, tasksInJob, machines,	minTime++);
			
			unsigned int n_p = 0;
			unsigned int n_b = 0;

			if (s->status() != SS_FAILED) {
				n_p = s->propagators();
				n_b = s->branchings();
			}

			Search::Stop* stop = FailTimeStop::create(fails, time);
			BAB<Scheduler> e(s,c_d,a_d,stop);
			delete s;
			do {
				Scheduler* ex = e.next();
				if (ex == NULL){
				//	solution = true;
					break;
				}
				solution = true;
				ex->print();
				ex->result(result);
				delete ex;
			} while (--i != 0);
			if(solution){/*
				Search::Statistics stat = e.statistics();
				cout << endl;
				cout << "Initial" << endl
					<< "\tpropagators:   " << n_p << endl
					<< "\tbranchings:    " << n_b << endl
					<< endl
					<< "Summary" << endl
					<< "\truntime:       " << t.stop() << endl
					<< "\tsolutions:     " << abs(static_cast<int>(solutions) - i) << endl
					<< "\tpropagations:  " << stat.propagate << endl
					<< "\tfailures:      " << stat.fail << endl
					<< "\tclones:        " << stat.clone << endl
					<< "\tcommits:       " << stat.commit << endl
					<< "\tpeak memory:   "
					<< static_cast<int>((stat.memory+1023) / 1024) << " KB"
					<< endl;*/
				*runtime = t.stop(); 
				printf("\n runtime: %f",*runtime);
			}
		}
	} catch (Exception e) {
		cout << "Exception: " << e.what() << "." << endl
			<< "Stopping..." << endl;
	}
	listOfActivities.clear();
	sortTable.clear();
}

Scheduler::~Scheduler(){
//TODO
}
Scheduler::Scheduler( int **& resource,  unsigned int **& duration, int iJobs, int iTasksInJob, int iMachines,unsigned int iMaxTime)
	: q(this,iTasksInJob*iJobs+1,0,iMaxTime),e(this,iTasksInJob*iJobs+1,0,iMaxTime),  best(this,0,iMaxTime+1) {
		
		jobs = iJobs;
		tasksInJob = iTasksInJob;
		machines = iMachines;	
		solve();		
	}

void Scheduler::solve(){

	IntArgs height(tasksInJob*jobs+1);
	IntArgs duration(tasksInJob*jobs+1);
	IntArgs limit(tasksInJob*jobs+1);   
	IntArgs machine(tasksInJob*jobs+1);

	std::vector<Activity>::iterator it1;
	std::vector<Activity>::iterator it;
	std::vector<unsigned int>::iterator it_pre;


	for(it = listOfActivities.begin(); it!=listOfActivities.end();it++){
		for( it_pre = it->prerequirements.begin(); it_pre != it->prerequirements.end(); it_pre++){
			post(this, tt((q[*it_pre] + listOfActivities.at(*it_pre).processingTime) <= q[it->id]));
		}
	}

	for(int i=0; i <= machines; i++){ 
		for(it = listOfActivities.begin(); it!=listOfActivities.end(); it++){
			if(it->resource == i){
				for(it1=it; it1!=listOfActivities.end(); it1++){
					if((it1->resource == i )&& (it1!=it) ){
						post(this,tt(~(q[it->id]+it->processingTime <= q[it1->id])||~(q[it1->id]+it1->processingTime <= q[it->id])));
						post(this,tt((e[it->id]<= q[it1->id])||(e[it1->id] <= q[it->id])));
						post(this,tt((e[it->id]+it1->processingTime <= e[it1->id])||(e[it1->id]+it->processingTime <= e[it->id])));
					}
				}
			}
		}
	};
	int i=0;
	for(it=listOfActivities.begin(); it!=listOfActivities.end();it++){
		height[i]=1;//each task requires 1 unit of resource
		duration[i]=it->processingTime;
		limit[i] = 1;//the machine has only one resource
		post(this, (e[i] - duration[i]) == q[i]);      
		machine[i++] = it->resource;	
	};

//	cumulatives(this, machine, q, duration, e, height,  limit, true,ICL_BND);

	post(this, best == q[jobs*tasksInJob]);
	branch(this,q, BVAR_REGRET_MIN_MIN,BVAL_MIN);
	//branch(this, q, BVAR_DEGREE_MIN, BVAL_MIN);
};

void Scheduler::result(unsigned int **& r){
	for(std::vector<SortTableElement>::iterator it = sortTable.begin(); it!=sortTable.end()-1; it++){
		std::cout << "[prev, actual] = [ ";
		std::cout << it->previous << ", ";
		std::cout << it->actual << " ]" << std::endl;
		r[(it->previous - it->previous%tasksInJob)/tasksInJob][it->previous%tasksInJob] = (unsigned int )q[it->actual].val();
	};
};


void Scheduler::print(){
	for (int i = 0; i < q.size(); i++) {

		std::cout << i << ": ";
		std::cout <<  "" << "[s, pt, m] = [";
		//	std::cout << q[i] << "," << q[i] << ", ";
		std::cout << q[i].val() << "] ";

		std::cout << std::endl;
	};
	std::cout << "------------"<< std::endl;

};

void Scheduler::constrain(Scheduler * iScheduler){
	rel(this, best, IRT_LE, static_cast<Scheduler*>(iScheduler)->best.val());
};

unsigned int Scheduler::copies = 0;

int main(int argc, char ** argv){
	double rtime;
	int size = 6;
	int **res;

	res = new int*[size];
	for( int x = 0; x < size ; x++ )
		res[x] = new int[size];
	unsigned int ** dur;
	dur = new unsigned int*[size];
	for( int x = 0; x < size; x++ )
		dur[x] = new unsigned int[size];


	dur[0][0]=1;dur[0][1]=3; dur[0][2]=6; dur[0][3]=7; dur[0][4]=3;dur[0][5]=6;
	dur[1][0]=8;dur[1][1]=5; dur[1][2]=10;dur [1][3]=10;dur[1][4]=10;dur[1][5]=4;
	dur[2][0]=5;dur[2][1]=4; dur[2][2]=8; dur [2][3]=9;dur[2][4]=1;dur[2][5]=7;
	dur[3][0]=5;dur[3][1]=5; dur[3][2]=5; dur [3][3]=3;dur[3][4]=8;dur[3][5]=9;
	dur[4][0]=9;dur[4][1]=3; dur[4][2]=5; dur [4][3]=4;dur[4][4]=3;dur[4][5]=1;
	dur[5][0]=3;dur[5][1]=3; dur[5][2]=9; dur [5][3]=10;dur[5][4]=4;dur[5][5]=1;
	
	res[0][0]=3;res[0][1]=1; res [0][2]=2; res[0][3]=4; res[0][4]=6; res[0][5]=5;
	res[1][0]=2;res[1][1]=3; res [1][2]=5; res[1][3]=6;res[1][4]=1;res[1][5]=4;
	res[2][0]=3;res[2][1]=4; res [2][2]=6; res[2][3]=1;res[2][4]=2;res[2][5]=5;
	res[3][0]=2;res[3][1]=1; res [3][2]=3; res[3][3]=4;res[3][4]=5;res[3][5]=6;
	res[4][0]=3;res[4][1]=2; res [4][2]=5; res[4][3]=6;res[4][4]=1;res[4][5]=4;
	res[5][0]=2;res[5][1]=4; res [5][2]=6; res[5][3]=1;res[5][4]=5;res[5][5]=3;
	
/*	
	dur[0][0]=1;dur[0][1]=3; dur[0][2]=6; dur[0][3]=7; dur[0][4]=3;dur[0][5]=3;
	dur[1][0]=8;dur[1][1]=5; dur[1][2]=10;dur [1][3]=10;dur[1][4]=3;dur[1][5]=1;
	dur[2][0]=5;dur[2][1]=4; dur[2][2]=8; dur [2][3]=9;dur[2][4]=3;dur[2][5]=5;
	dur[3][0]=5;dur[3][1]=5; dur[3][2]=5; dur [3][3]=3;dur[3][4]=3;dur[3][5]=3;
	dur[4][0]=5;dur[4][1]=1; dur[4][2]=13; dur [4][3]=1;dur[4][4]=3;dur[4][5]=2;
	dur[5][0]=8;dur[5][1]=9; dur[5][2]=1; dur [5][3]=6;dur[5][4]=1;dur[5][5]=3;
	
	res[0][0]=3;res[0][1]=1; res[0][2]=2; res[0][3]=4; res[0][4]=1; res[0][5]=5;
	res[1][0]=1;res[1][1]=3; res [1][2]=4; res[1][3]=3;res[0][4]=5;res[1][5]=2;
	res[2][0]=3;res[2][1]=4; res[2][2]=2; res[2][3]=6;res[0][4]=5;res[2][5]=3;
	res[3][0]=2;res[3][1]=1; res [3][2]=3; res[3][3]=4;res[0][4]=1;res[3][5]=1;
	res[4][0]=4;res[4][1]=1; res [4][2]=4; res[4][3]=6;res[4][4]=2;res[4][5]=4;
	res[5][0]=3;res[5][1]=5; res [5][2]=3; res[5][3]=5;res[5][4]=2;res[5][5]=4;
	
*/
	/*
	dur[0][0]=1;dur[0][1]=3; dur[0][2]=6; dur[0][3]=7; dur[0][4]=3;
	dur[1][0]=8;dur[1][1]=5; dur[1][2]=10;dur [1][3]=10;dur[1][4]=3;
	dur[2][0]=5;dur[2][1]=4; dur[2][2]=8; dur [2][3]=9;dur[2][4]=3;
	dur[3][0]=5;dur[3][1]=5; dur[3][2]=5; dur [3][3]=3;dur[3][4]=3;
	dur[4][0]=5;dur[4][1]=1; dur[4][2]=13; dur [4][3]=1;dur[4][4]=3;
	
	res[0][0]=3;res[0][1]=1; res[0][2]=2; res[0][3]=4; res[0][4]=1;
	res[1][0]=1;res[1][1]=3; res [1][2]=4; res[1][3]=3;res[1][4]=5;
	res[2][0]=3;res[2][1]=4; res[2][2]=2; res[2][3]=1;res[2][4]=5;
	res[3][0]=2;res[3][1]=1; res [3][2]=3; res[3][3]=4;res[3][4]=1;
	res[4][0]=4;res[4][1]=1; res [4][2]=4; res[4][3]=4;res[4][4]=2;
*/
	for(int i=0; i < size; i++){
		for(int j =0 ; j< size; j++)
			 res[i][j] = res[i][j]-1;
	}
	unsigned int **r;
	r = new unsigned int*[size];//tasksinjob
	for( int x = 0; x < size; x++ )
		r[x] = new unsigned int[size];//jobs

	run(res,dur,size,size,size,r,&rtime);
	std::cout <<  "\n Start time: \n " <<std::endl;
	for(int i=0; i < size; i++){
		for(int j =0 ; j< size; j++){
			std::cout << r[i][j] << " ";
	}
		std::cout <<  " " <<std::endl;
	}

	std::cout <<  "\n Duration: \n " <<std::endl;
	for(int i=0; i < size; i++){
		for(int j =0 ; j< size; j++){
			std::cout << dur[i][j] << " ";
		}
		std::cout <<  " " <<std::endl;
	}
	
	std::cout <<  "\n Resource: \n " <<std::endl;
	for(int i=0; i < size; i++){
		for(int j =0 ; j< size; j++){
			std::cout << res[i][j] << " ";
		}
		std::cout <<  " " <<std::endl;
	}
		
	//TODO better cleanup
	delete res;
	delete dur;
	delete r;
/*
	int **res;
	res = new int*[4];
	for( int x = 0; x < 4; x++ )
		res[x] = new int[4];
	unsigned int ** dur;
	dur = new unsigned int*[4];
	for( int x = 0; x < 4; x++ )
		dur[x] = new unsigned int[4];
	dur[0][0]=1;dur[0][1]=3; dur[0][2]=6; dur[0][3]=7;
	dur[1][0]=8;dur[1][1]=5; dur[1][2]=10;dur [1][3]=10;
	dur[2][0]=5;dur[2][1]=4; dur[2][2]=8; dur [2][3]=9;
	dur[3][0]=5;dur[3][1]=5; dur[3][2]=5; dur [3][3]=3;
	
	res[0][0]=3;res[0][1]=1; res[0][2]=2; res[0][3]=4;
	res[1][0]=1;res[1][1]=3; res [1][2]=4; res[1][3]=3;
	res[2][0]=3;res[2][1]=4; res[2][2]=2; res[2][3]=1;
	res[3][0]=2;res[3][1]=1; res [3][2]=3; res[3][3]=4;

	unsigned int **r;
	r = new unsigned int*[4];//tasksinjob
	for( int x = 0; x < 4; x++ )
		r[x] = new unsigned int[4];//jobs

	run(res,dur,opt,4,4,4,100,r);
	for(int i=0; i < 4; i++){
		for(int j =0 ; j< 4; j++){
			std::cout << r[i][j] << " ";
		}
		std::cout <<  " " <<std::endl;
	}
		
	//TODO better cleanup
	delete res;
	delete dur;
	delete r;
	*/
}


